package com.practice.zuocy.trainingcamp001.class01;

import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;

/**
 * 【题目】：（TODO：单调栈）
 * 在数组中想找到一个数， 左边和右边比这个数小、 且离这个数最近的位置。
 * 如果对每一个数都想求这样的信息， 能不能整体代价达到O(N)？
 * 需要使用到单调栈结构
 * 单调栈结构的原理和实现
 */
public class Code03_MonotonousStack {

	/*
	 * 求里你最近比你小的数， 栈底--->栈顶 ： 小 ---> 大，
	 * 一个东西从栈中出来时生成记录，让你出来的数是右边离你最近比你小的（没有就是null），栈中你压着的数是左边离你最近比你小的（没有就是null）
	 * 最后单独处理栈中剩余的记录（依次弹出，出来时按照上面的规则得到左边距离它最近比它小的数、右边距离它最近比它小的数都是null）
	 *
	 * 求里你最近比你大的数， 栈底--->栈顶 ： 大 ---> 小，
	 * 一个东西从栈中出来时生成记录，让你出来的数是右边离你最近比你大的（没有就是null），栈中你压着的数是左边离你最近比你大的（没有就是null）
	 * 最后单独处理栈中剩余的记录（依次弹出，出来时按照上面的规则得到左边距离它最近比它大的数、右边距离它最近比它大的数都是null）
	 *
	 * 栈中放的值下标，是index
	 *
	 * 如果有重复值，栈中存放的每个元素就是index的列表，LinkedList<Integer>, 例如 [index1, index2, index3...indexN]
	 * 放入一个数时，如果发现其与栈顶代表的值相等，直接将其下标放到栈顶列表的末尾
	 * 每次弹出，弹出的是一个列表，左边比他们小的离他们最近的是其小面压着的列表中最末尾的元素
	 *
	 */

	// 没有重复值的情况
	public static int[][] getNearLessNoRepeat(int[] arr) {
		int[][] res = new int[arr.length][2];
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < arr.length; i++) {
			while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
				int popIndex = stack.pop();
				int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
				res[popIndex][0] = leftLessIndex;
				res[popIndex][1] = i;
			}
			stack.push(i);
		}
		while (!stack.isEmpty()) {
			int popIndex = stack.pop();
			int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
			res[popIndex][0] = leftLessIndex;
			res[popIndex][1] = -1;
		}
		return res;
	}

	// arr [3, 2, 1, 4, 5]
	//      0  1  2  3  4
	
	//  [
	//    0 :  [-1,  1  ]
	//    1 :  [-1,  2  ]
	
	//  ] 
	//
	// 有重复值的情况
	public static int[][] getNearLess(int[] arr) {
		int[][] res = new int[arr.length][2];
		
		
		// List<Integer> -> 放的是位置，同样值的东西，位置压在一起
		// 代表值    底  ->  顶   小  -> 大
		Stack<List<Integer>> stack = new Stack<>();
		for (int i = 0; i < arr.length; i++) { // i -> arr[i] 进栈
			// 底 -> 顶， 小 -> 大
			while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
				List<Integer> popIs = stack.pop();
				// 取位于下面位置的列表中，最晚加入的那个
				int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
				for (Integer popi : popIs) {
					res[popi][0] = leftLessIndex;
					res[popi][1] = i;
				}
			}
			// 相等的、比你小的
			if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
				stack.peek().add(Integer.valueOf(i));
			} else {
				ArrayList<Integer> list = new ArrayList<>();
				list.add(i);
				stack.push(list);
			}
		}
		while (!stack.isEmpty()) {
			List<Integer> popIs = stack.pop();
			// 取位于下面位置的列表中，最晚加入的那个
			int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
			for (Integer popi : popIs) {
				res[popi][0] = leftLessIndex;
				res[popi][1] = -1;
			}
		}
		return res;
	}

	public static int[][] myAnswerCanRepeat(int[] arr){
		// res[i][0]代表arr[i]左边离它最近比它小的数的下标, res[i][1]代表arr[i]右边离它最近比它小的数的下标
		int[][] res = new int[arr.length][2];
		Stack<LinkedList<Integer>> stack = new Stack<>();
		int i = 0;
		while (i < arr.length){
			if (!stack.isEmpty()){
				LinkedList<Integer> topIndexList = stack.peek();
				Integer index = topIndexList.get(0);
				if (arr[index] < arr[i]){
					// 进
					LinkedList<Integer> curIndexList = new LinkedList<>();
					curIndexList.add(i);
					stack.push(curIndexList);
					i++;
				}else if (arr[index]==arr[i]){
					// 进
					topIndexList.add(i);
					i++;
				}else {
					// 弹
					LinkedList<Integer> popIndexList = stack.pop();
					LinkedList<Integer> nextIndexList = null;
					if (!stack.isEmpty()){
						nextIndexList= stack.peek();
					}
					for (int j = 0; j < popIndexList.size(); j++) {
						Integer tempIndex = popIndexList.get(j);
						if (nextIndexList == null){
							res[tempIndex][0] = -1;
						}else {
							res[tempIndex][0] = nextIndexList.get(nextIndexList.size()-1);
						}
						res[tempIndex][1] = i;
					}
					// i不变，继续在循环中跟栈顶比较
				}
			}else {
				LinkedList<Integer> curIndexList = new LinkedList<>();
				curIndexList.add(i);
				stack.push(curIndexList);
				i++;
			}
		}

		// 将栈中剩余的列表弹出
		while (!stack.isEmpty()){
			LinkedList<Integer> popIndexList = stack.pop();
			LinkedList<Integer> nextIndexList = null;
			if (!stack.isEmpty()){
				nextIndexList= stack.peek();
			}
			for (int j = 0; j < popIndexList.size(); j++) {
				Integer tempIndex = popIndexList.get(j);
				if (nextIndexList == null){
					res[tempIndex][0] = -1;
				}else {
					res[tempIndex][0] = nextIndexList.get(nextIndexList.size()-1);
				}
				res[tempIndex][1] = -1;
			}
		}
		return res;
	}














	// for test
	public static int[] getRandomArrayNoRepeat(int size) {
		int[] arr = new int[(int) (Math.random() * size) + 1];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = i;
		}
		for (int i = 0; i < arr.length; i++) {
			int swapIndex = (int) (Math.random() * arr.length);
			int tmp = arr[swapIndex];
			arr[swapIndex] = arr[i];
			arr[i] = tmp;
		}
		return arr;
	}

	// for test
	public static int[] getRandomArray(int size, int max) {
		int[] arr = new int[(int) (Math.random() * size) + 1];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) (Math.random() * max) - (int) (Math.random() * max);
		}
		return arr;
	}

	// for test
	public static int[][] rightWay(int[] arr) {
		int[][] res = new int[arr.length][2];
		for (int i = 0; i < arr.length; i++) {
			int leftLessIndex = -1;
			int rightLessIndex = -1;
			int cur = i - 1;
			while (cur >= 0) {
				if (arr[cur] < arr[i]) {
					leftLessIndex = cur;
					break;
				}
				cur--;
			}
			cur = i + 1;
			while (cur < arr.length) {
				if (arr[cur] < arr[i]) {
					rightLessIndex = cur;
					break;
				}
				cur++;
			}
			res[i][0] = leftLessIndex;
			res[i][1] = rightLessIndex;
		}
		return res;
	}

	// for test
	public static boolean isEqual(int[][] res1, int[][] res2) {
		if (res1.length != res2.length) {
			return false;
		}
		for (int i = 0; i < res1.length; i++) {
			if (res1[i][0] != res2[i][0] || res1[i][1] != res2[i][1]) {
				return false;
			}
		}

		return true;
	}

	// for test
	public static void printArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int size = 10;
		int max = 20;
		int testTimes = 2000000;
		for (int i = 0; i < testTimes; i++) {
			int[] arr1 = getRandomArrayNoRepeat(size);
			int[] arr2 = getRandomArray(size, max);
			int[] arr3 = getRandomArray(size, max);
			if (!isEqual(getNearLessNoRepeat(arr1), rightWay(arr1))) {
				System.out.println("Oops!");
				printArray(arr1);
				break;
			}
			if (!isEqual(getNearLess(arr2), rightWay(arr2))) {
				System.out.println("Oops!");
				printArray(arr2);
				break;
			}
			if (!isEqual(myAnswerCanRepeat(arr3), rightWay(arr3))) {
				System.out.println("Oops!");
				printArray(arr3);
				break;
			}
		}
		System.out.println("niubila");
	}
}
